namespace AdvancedTraining.Lesson51;

/// <summary>
/// 可编程机器人问题 - LeetCode LCP 03
/// 使用状态压缩和位运算判断机器人是否能够到达目标位置
/// </summary>
public class ProgrammableRobot //leetcode_lcp_03
{
    // 此处为一轮以内，x和y最大能移动的步数，对应的2的几次方
    // 比如本题，x和y最大能移动1000步，就对应2的10次方
    // 如果换一个数据量，x和y最大能移动5000步，就对应2的13次方
    // 只需要根据数据量修改这一个变量，剩下的代码不需要调整
    private const int Bit = 10;

    // 如果，x和y最大能移动的步数，对应2的bit次方
    // 那么一个坐标(x,y)，所有的可能性就是：(2 ^ bit) ^ 2 = 2 ^ (bit * 2)
    // 也就是，(1 << (bit << 1))个状态，记为bits
    private const int Bits = 1 << (Bit << 1);

    // 为了表示下bits个状态，需要几个整数？
    // 32位只需要一个整数，所以bits个状态，需要bits / 32 个整数
    // 即整型长度需要 : bits >> 5
    private static readonly int[] Set = new int[Bits >> 5];

    /// <summary>
    /// 判断机器人是否能到达目标位置（方法一：使用HashSet）
    /// 算法思路：状态压缩 + 哈希表
    /// 1. 执行一轮命令，记录所有可能到达的位置
    /// 2. 判断目标位置是否在可达位置集合中
    /// 3. 检查障碍物是否阻挡了到达目标的路径
    /// 时间复杂度：O(N + M)，其中N为命令长度，M为障碍物数量
    /// 空间复杂度：O(N)
    /// </summary>
    /// <param name="command">命令字符串，只包含'R'和'U'</param>
    /// <param name="obstacles">障碍物数组</param>
    /// <param name="x">目标x坐标</param>
    /// <param name="y">目标y坐标</param>
    /// <returns>是否能到达目标位置</returns>
    public static bool Robot1(string command, int[][] obstacles, int x, int y)
    {
        var x1 = 0;
        var y2 = 0;
        var set = new HashSet<int> { 0 };
        foreach (var c in command)
        {
            x1 += c == 'R' ? 1 : 0;
            y2 += c == 'U' ? 1 : 0;
            set.Add((x1 << Bit) | y2);
        }

        // 不考虑任何额外的点，机器人能不能到达，(x，y)
        if (!Meet1(x, y, x1, y2, set)) return false;
        foreach (var ob in obstacles)
            // ob[0] ob[1]
            if (ob[0] <= x && ob[1] <= y && Meet1(ob[0], ob[1], x1, y2, set))
                return false;
        return true;
    }

    /// <summary>
    /// 判断机器人是否能到达目标位置（方法二：使用位运算数组）
    /// 算法思路：状态压缩 + 位运算
    /// 1. 使用位数组代替HashSet，提高空间效率
    /// 2. 每个bit代表一个坐标状态
    /// 3. 通过位运算快速判断状态是否存在
    /// 时间复杂度：O(N + M)，其中N为命令长度，M为障碍物数量
    /// 空间复杂度：O(2^(2*Bit) / 32)
    /// </summary>
    /// <param name="command">命令字符串，只包含'R'和'U'</param>
    /// <param name="obstacles">障碍物数组</param>
    /// <param name="x">目标x坐标</param>
    /// <param name="y">目标y坐标</param>
    /// <returns>是否能到达目标位置</returns>
    public static bool Robot2(string command, int[][] obstacles, int x, int y)
    {
        Array.Fill(Set, 0);
        Set[0] = 1;
        var x1 = 0;
        var y1 = 0;
        foreach (var c in command)
        {
            x1 += c == 'R' ? 1 : 0;
            y1 += c == 'U' ? 1 : 0;
            Add((x1 << Bit) | y1);
        }

        if (!Meet2(x, y, x1, y1)) return false;
        foreach (var ob in obstacles)
            if (ob[0] <= x && ob[1] <= y && Meet2(ob[0], ob[1], x1, y1))
                return false;
        return true;
    }

    /// <summary>
    /// 判断坐标是否可达（HashSet版本）
    /// </summary>
    /// <param name="x">目标x坐标</param>
    /// <param name="y">目标y坐标</param>
    /// <param name="x1">一轮内x方向移动步数</param>
    /// <param name="y1">一轮内y方向移动步数</param>
    /// <param name="set">可达位置集合</param>
    /// <returns>是否可达</returns>
    private static bool Meet1(int x, int y, int x1, int y1, HashSet<int> set)
    {
        if (x1 == 0)
            // Y != 0 往上肯定走了！
            return x == 0;
        if (y1 == 0) return y == 0;
        // 至少几轮？
        var atLeast = Math.Min(x / x1, y / y1);
        // 经历过最少轮数后，x剩多少？
        var rx = x - atLeast * x1;
        // 经历过最少轮数后，y剩多少？
        var ry = y - atLeast * y1;
        return set.Contains((rx << Bit) | ry);
    }

    /// <summary>
    /// 判断坐标是否可达（位运算版本）
    /// </summary>
    /// <param name="x">目标x坐标</param>
    /// <param name="y">目标y坐标</param>
    /// <param name="x1">一轮内x方向移动步数</param>
    /// <param name="y1">一轮内y方向移动步数</param>
    /// <returns>是否可达</returns>
    private static bool Meet2(int x, int y, int x1, int y1)
    {
        if (x1 == 0) return x == 0;
        if (y1 == 0) return y == 0;
        var atLeast = Math.Min(x / x1, y / y1);
        var rx = x - atLeast * x1;
        var ry = y - atLeast * y1;
        return Contains((rx << Bit) | ry);
    }

    /// <summary>
    /// 在位数组中添加状态
    /// </summary>
    /// <param name="status">要添加的状态</param>
    private static void Add(int status)
    {
        Set[status >> 5] |= 1 << (status & 31);
    }

    /// <summary>
    /// 检查位数组中是否包含状态
    /// </summary>
    /// <param name="status">要检查的状态</param>
    /// <returns>是否包含</returns>
    private static bool Contains(int status)
    {
        return status < Bits && (Set[status >> 5] & (1 << (status & 31))) != 0;
    }

    /// <summary>
    /// 打印整数的二进制表示（用于调试）
    /// </summary>
    /// <param name="num">要打印的整数</param>
    private static void PrintBinary(int num)
    {
        for (var i = 31; i >= 0; i--) Console.Write((num & (1 << i)) != 0 ? "1" : "0");
        Console.WriteLine();
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 可编程机器人问题测试 ===");

        // 测试用例1: 基本功能测试
        Test1();

        // 测试用例2: 障碍物阻挡
        Test2();

        // 测试用例3: 复杂路径
        Test3();

        // 测试用例4: 边界情况
        Test4();

        // 测试用例5: 大坐标测试
        Test5();

        // 演示位运算状态压缩原理
        DemoStateCompression();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("状态压缩：将(x,y)坐标编码为整数，使用位运算存储");
        Console.WriteLine("两种方法：HashSet存储和位数组存储");
        Console.WriteLine("一轮计算：执行一轮命令，记录所有可达位置");
        Console.WriteLine("多轮判断：通过数学计算判断目标是否在路径上");
        Console.WriteLine("时间复杂度：O(N + M)，空间复杂度：O(N) 或 O(2^(2*Bit)/32)");
    }

    /// <summary>
    /// 测试用例1: 基本功能测试
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: 基本功能测试");
        string command = "URR";
        int[][] obstacles = [];
        int x = 3, y = 2;
        var result1 = Robot1(command, obstacles, x, y);
        var result2 = Robot2(command, obstacles, x, y);
        Console.WriteLine($"命令: {command}");
        Console.WriteLine($"目标: ({x}, {y})");
        Console.WriteLine($"障碍物: 无");
        Console.WriteLine($"方法1结果: {result1} (期望: true)");
        Console.WriteLine($"方法2结果: {result2} (期望: true)");
    }

    /// <summary>
    /// 测试用例2: 障碍物阻挡
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: 障碍物阻挡");
        string command = "URR";
        int[][] obstacles = [[2, 1]];
        int x = 3, y = 2;
        var result1 = Robot1(command, obstacles, x, y);
        var result2 = Robot2(command, obstacles, x, y);
        Console.WriteLine($"命令: {command}");
        Console.WriteLine($"目标: ({x}, {y})");
        Console.WriteLine($"障碍物: [{string.Join(", ", obstacles.Select(o => $"({o[0]},{o[1]})"))}]");
        Console.WriteLine($"方法1结果: {result1} (期望: false)");
        Console.WriteLine($"方法2结果: {result2} (期望: false)");
    }

    /// <summary>
    /// 测试用例3: 复杂路径
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 复杂路径");
        string command = "URURR";
        int[][] obstacles = [[3, 2], [1, 1]];
        int x = 5, y = 3;
        var result1 = Robot1(command, obstacles, x, y);
        var result2 = Robot2(command, obstacles, x, y);
        Console.WriteLine($"命令: {command}");
        Console.WriteLine($"目标: ({x}, {y})");
        Console.WriteLine($"障碍物: [{string.Join(", ", obstacles.Select(o => $"({o[0]},{o[1]})"))}]");
        Console.WriteLine($"方法1结果: {result1} (期望: true)");
        Console.WriteLine($"方法2结果: {result2} (期望: true)");
    }

    /// <summary>
    /// 测试用例4: 边界情况
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 边界情况");
        string command = "R";
        int[][] obstacles = [[1, 0]];
        int x = 1000, y = 0;
        var result1 = Robot1(command, obstacles, x, y);
        var result2 = Robot2(command, obstacles, x, y);
        Console.WriteLine($"命令: {command}");
        Console.WriteLine($"目标: ({x}, {y})");
        Console.WriteLine($"障碍物: [{string.Join(", ", obstacles.Select(o => $"({o[0]},{o[1]})"))}]");
        Console.WriteLine($"方法1结果: {result1} (期望: false)");
        Console.WriteLine($"方法2结果: {result2} (期望: false)");
    }

    /// <summary>
    /// 测试用例5: 大坐标测试
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 大坐标测试");
        string command = "URRU";
        int[][] obstacles = [];
        int x = 100, y = 50;
        var result1 = Robot1(command, obstacles, x, y);
        var result2 = Robot2(command, obstacles, x, y);
        Console.WriteLine($"命令: {command}");
        Console.WriteLine($"目标: ({x}, {y})");
        Console.WriteLine($"障碍物: 无");
        Console.WriteLine($"方法1结果: {result1}");
        Console.WriteLine($"方法2结果: {result2}");
        Console.WriteLine($"两种方法结果一致: {result1 == result2}");
    }

    /// <summary>
    /// 演示位运算状态压缩原理
    /// </summary>
    private static void DemoStateCompression()
    {
        Console.WriteLine("\n=== 位运算状态压缩原理演示 ===");
        var x = 7;
        Console.Write($"x = {x} 的二进制: ");
        PrintBinary(x);

        var y = 4;
        Console.Write($"y = {y} 的二进制: ");
        PrintBinary(y);

        // x_y 组合！
        var c = (x << Bit) | y;
        Console.Write($"(x << {Bit}) | y = {c} 的二进制: ");
        PrintBinary(c);
        Console.WriteLine($"组合结果: {c}");

        Console.WriteLine("\n状态压缩说明:");
        Console.WriteLine($"- 每个坐标范围: 0 ~ 2^{Bit} - 1 (0 ~ {Math.Pow(2, Bit) - 1})");
        Console.WriteLine($"- 总状态数: 2^(Bit*2) = 2^{Bit * 2} = {Math.Pow(2, Bit * 2)}");
        Console.WriteLine($"- 位数组大小: {Bits} / 32 = {Bits >> 5} 个整数");
        Console.WriteLine($"- 状态编码: (x << {Bit}) | y，将二维坐标编码为一维整数");
    }
}